import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: XMQ
 * Date: 2022-05-09
 * Time: 11:09
 */
//两个经典递归问题
public class Test {
    /*
    跳台阶
     */
    public static int jump(int n){
        if(n == 1){
            return 1;
        }else if(n == 2){
            return 2;
        }else{
            return jump(n-1)+(n-2);
        }
    }
    public static void main(String[] args) {
        //终止条件   n = 1 只有1种跳法  n = 2只有2种跳法
        //递推公式   n>2 sum(n) = sum(n-1)+sum(n-2);
        Scanner n = new Scanner(System.in);
        int ret = jump(n.nextInt());
        System.out.println(ret);
    }
    /*
    递归之汉诺塔
    1   A->C  1  2^1-1
    2   A->B  A->C  B->C  3  2^2-1
    3   A->C  A->B  C->B  A->C  B->A  B->C  A->C    7  2^3-1
    ……
    64  2^64-1  1.6G的电脑需要移300年左右
     */
    public static void mov(char pos1,char pos3){
        System.out.print(pos1+"->"+pos3+" ");
    }

    /**
     *
     * @param n   盘子数
     * @param pos1   第一个位置   刚开始（初始位置）
     * @param pos2   第二个位置        （中途位置）
     * @param pos3   第三个位置        （终止位置）
     */
    public static void hanoi(int n,char pos1, char pos2, char pos3){
        if( n == 1){
            mov(pos1,pos3);
        }else{
            hanoi(n-1,pos1,pos3,pos2);
            mov(pos1,pos3);
            hanoi(n-1,pos2,pos1,pos3);
        }

    }
    public static void main1(String[] args) {
        //终止条件  一个盘子的移动
        //递推公式  n个盘子的移动 = 一个盘子 + n-1个盘子的移动
        hanoi(1,'A','B','C');
        System.out.println();
        hanoi(2,'A','B','C');
        System.out.println();
        hanoi(3,'A','B','C');
        System.out.println();
        hanoi(4,'A','B','C');
    }
}
